/*
求最大公约数的两种算法
1. 更相减损法
	两个整数a、b（a>b），它们的最大公约数为a-b的值c和较小的数b的最大公约数。
2. 辗转相除法
	两个整数a、b（a>b），它们的最大公约数是a取b的模c和较小的数b的最大公约数。
两种方法未必要严格使得第一个参数大于第二个参数（GcdSub里会判断，GcdMod里多翻转一步就会使其翻转）
虽然都能得到正确结果，但是GcdMod里所需时间会翻倍，因此还是不建议随意放置。尽量保证第一个参数大于第二个
*/
#include <iostream>
using namespace std;

int GcdSub(int m,int n){
	if(m == n){
		return m;
	}
	if(m < n){
		return GcdSub(m,n-m);
	}
	else{
		return GcdSub(m-n,n);
	}
}
int GcdMod(int m,int n){
	// if(n == 0){
	// 	return m;
	// }
	// else{
	// 	return GcdMod(n,m%n);
	// }
	return n?GcdMod(n,m%n):m;
}
int Gcd(int m,int n){
	if(m == n){
		return m;
	}
	if(n == 0){
		return m;
	}
	if(m == 0){
		return n;
	}
	if(~m & 1){	//m是偶数
		if(n & 1){	//n是奇数
			return Gcd(n,m>>1);
		}
		else{
			return Gcd(m>>1,n>>1)<<1;
		}
	}
	if(~n&1){	//m为奇数，n为偶
		return Gcd(m,n>>1);
	}
	if(m>n){
		return Gcd((m-n),n);
	}
	return Gcd((n-m),m);	//差和较小的数
}
int main(int argc, char const *argv[])
{
	cout<<GcdMod(954167238,2147483646)<<endl;
	cout<<Gcd(2147483646,954167238)<<endl;
	return 0;
}